package com.leetcode.array_matrix;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/10/11 18:16
 */
public class IntervalIntersection_986 {

    public int[][] intervalIntersection(int[][] A, int[][] B) {
        // 已经排序
        int a = 0, b = 0; // A B 组的游标
        List<int[]> res = new ArrayList<>();

        // 必须同时满足，有一个不满足，那么一定是空集
        while (a < A.length && b < B.length) {
            int startA = A[a][0], endA = A[a][1], startB = B[b][0], endB = B[b][1];
            // 超过了最大极限，一定没有交集
            if (startA > endB) {
                b++;
            } else if (startB > endA) {
                a++;
            } else {
                // 交集，起点选较大值，终点选较小值
                int start = Math.max(startA, startB);
                int end = Math.min(endA, endB);
                res.add(new int[]{start, end});

                // 只需要比较末尾，进行游标移动
                if (endA < endB) {
                    a++;
                } else if (endA > endB) {
                    b++;
                } else {
                    a++;
                    b++;
                }
            }
        }
        return res.toArray(new int[0][]);
    }

}
